package tree;

import javax.swing.*;
import java.util.LinkedList;
import java.util.Queue;



class Node {
    String val;
    Node left;//左子树
    Node right;//右子树
    public Node(String val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }

    @Override
    public String toString() {
        return "Node{" +
                "val='" + val + '\'' +
                ", left=" + left +
                ", right=" + right +
                '}';
    }
}class Tree{
    public Node root;
}


public class Test1 {
    //通过这个方法手动创建一棵树
    public  static Node createTree() {
        //先把所有节点都创建出来
        Node A = new Node("A");
        Node B = new Node("B");
        Node C = new Node("C");
        Node D = new Node("D");
        Node E = new Node("E");
        Node F = new Node("F");
        Node G = new Node("G");
        //然后把他们连起来
        A.left = B;
        A.right = C;
        B.left = D;
        B.right = E;
        C.left = F;
        C.right = G;
        //最后返回根节点
        return A;

    }
    //先序遍历，访问操作就是打印，先访问根节点，然后左子树，最后右子树
    //递归实现
    public static void preOrder(Node root) {
        if(root==null){
            return ; //空树，返回
        }
        System.out.print(root.val); //先访问根节点
        preOrder(root.left); //左子树
        preOrder(root.right); //右子树
    }
    //中序遍历 就是先左子树，然后访问根节点，最后右子树
    public static void inOrder(Node root) {
        if(root==null){
            return ; //空树，返回
        }
        inOrder(root.left); //左子树
        System.out.print(root.val); //访问根节点
        inOrder(root.right); //右子树、
    }
    //后序遍历 就是先左子树，然后右子树，最后访问根节点
    public static void postOrder(Node root) {
        if(root==null){
            return ; //空树，返回
        }
        postOrder(root.left); //左子树
        postOrder(root.right); //右子树
        System.out.print(root.val); //访问根节点
    }
    //层序遍历 就是按层遍历树，从上到下，从左到右
    public static void levelOrder(Node root) {
        if (root == null) {
            return; //空树，返回
        }
        //创建一个队列
        Queue<Node> queue = new LinkedList<>();
        queue.add(root); //根节点入队
        while (!queue.isEmpty()) {
            Node node = queue.poll(); //队首出队
            System.out.print(node.val); //访问节点
            if (node.left != null) {
                queue.add(node.left); //左子树入队
            }
            if (node.right != null) {
                queue.add(node.right); //右子树入队
            }
        }
    }
    //求二叉树节点个数
    //方法1：public static int size = 0;//如果在递归函数中修改全局变量，会导致结果不准确，所以用一个静态变量来记录节点个数
    public static int size(Node root) {
        if (root == null) {
            return 0; //空树，返回0
        }
//        int size =0;
//        size++;
//         size(root.left);
//         size(root.right);//这个方法会导致结果不准确，因为递归函数中修改了全局变量size，导致结果不准确
//        return size;//也可以这样写；
        return 1 + size(root.left) + size(root.right);//方法二：递归计算左右子树的节点个数，然后加上根节点的个数
        //根节点+左+右=总节点数
    }
    //求叶子节点个数
    //就是左子树和右子树都为空的节点
    public static int getleafSize(Node root){
        if(root==null){
            return 0;
        }
        if(root.left==null&&root.right==null){
            return 1;
        }
        //如果左右子树都不为空，则递归计算左右子树的叶子节点个数
        return getleafSize(root.left)+getleafSize(root.right);
    }
    //获取第k层节点个数
    public static int getKLevelNodeCount(Node root,int k) {
        if (root == null) {
            return 0;
        }
        if(k<1){
            System.out.println("k值必须大于0");
        }
        if(k==1){//如果是第1层，则只需要返回根节点
            return 1;
        }
         return getKLevelNodeCount(root.left,k-1)+getKLevelNodeCount(root.right,k-1);
        //要计算第k层的节点个数，就是需要计算k-1层递归的返回值
    }
    //求二叉树高度
    //求左子树和右子树的最大值高度，然后加上根节点的高度
    public static  int getHeight(Node root) {
    if(root==null){
        return 0;
    }
    int leftHeight=getHeight(root.left);
    int rightHeight=getHeight(root.right);
    if(leftHeight>rightHeight){
        return leftHeight+1;
    }
    else {
        return rightHeight+1;
    }
    }

    // 检测值为value的元素是否存在
    public static Node find(Node root, String value){
        if(root==null){
            return null;
        }
        if(root.val.equals(value)){
            return root;
        }
        Node left=find(root.left,value);
        if(left!=null){
            return left;
        }
        return find(root.right,value);
//        Node right=find(root.right,value);
//        if(right!=null){
//            return right;
//        }
//        return null;
    }

    //判断整棵树是不是完全二叉树
    public static boolean isCompleteTree(Node root) {
        if (root == null) {
            return true;//空树，返回true
        }
        boolean isFirst = true; //是否是第一次遍历
        //针对树进行层序遍历
        Queue<Node> queue = new LinkedList<>();
        queue.offer(root); //根节点入队
        while (!queue.isEmpty()) {
            Node node = queue.poll(); //队首出队
            if(isFirst){
                //进入一阶段
                if(node.left==null&&node.right==null){
                    //没有子树，进入二阶段
                    isFirst=false;
                }else if(node.left!=null&&node.right==null){
                    //只有左子树，
                    isFirst=false;
                    //左子树入队列
                    queue.offer(node.left);
                }else if(node.left==null&&node.right!=null){
                    //只有右子树。返回false
                    return false;
                }else{
                    queue.offer(node.left);
                    queue.offer(node.right);
                }
            }else{
                //进入二阶段
                if(node.left!=null||node.right!=null){
                    //有子树，返回false
                    return false;
                }
                //没有子树，继续遍历下一个节点，由于没有子树，所以不用入队
            }
        }
        return true; //如果遍历完了，则是完全二叉树
    }

    public static void main(String[] args) {
        //root就表示树的根节点
        //Node root = new Node("A");
//        //也可以这样斌表示树 就是封装一下
//        Tree tree = new Tree();
        Node root = createTree();
        //先序遍历
        preOrder(root);//ABDECFG
        System.out.println();
        //中序遍历
        inOrder(root);//DBEAFCG
        //后序遍历
        System.out.println();
        postOrder(root);//DEBFGCA
        //层序遍历
        System.out.println();
        levelOrder(root);//ABCDEFG
        //求二叉树节点个数
        System.out.println("二叉树节点个数为："+size(root));//二叉树节点个数为：7

        //求叶子节点个数
        System.out.println("叶子节点个数为："+getleafSize(root));//叶子节点个数为：4

        //获取第k层节点个数
        System.out.println("第2层节点个数为："+getKLevelNodeCount(root,2));//第2层节点个数为：2

        //获取二叉树高度
        System.out.println("二叉树高度为："+getHeight(root));//二叉树高度为：3

        //检测值为value的元素是否存在
        System.out.println("是否存在值为B的节点："+(find(root,"B")));//是否存在值为B的节点：Node{val='B', left=Node{val='D', left=null, right=null}, right=Node{val='E', left=null, right=null}}

        //检测整棵树是不是完全二叉树
        System.out.println("是否是完全二叉树："+isCompleteTree(root));//是否是完全二叉树：true
    }
}
